package twice.class_monotonicstack;

import java.util.Stack;
//https://leetcode.cn/problems/largest-rectangle-in-histogram/submissions/
public class Class03_LargestRectangleInHistogram{
    public static int largestRectangleArea1(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int maxArea = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                maxArea = Math.max(maxArea,(i-k-1)*height[j]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            maxArea = Math.max(maxArea,(height.length-k-1)*height[j]);
        }

        return maxArea;
    }
}
